package com.xiyou.leetcode.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
 *
 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 *
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 *
 *示例 2:
 *
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 *  
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 5000
 *
 */
public class BuildTree {
    /**
     * key是树的值，value是中序遍历该节点所在的位置下标
     */
    private Map<Integer, Integer> indexMap = new HashMap<>();

    /**
     * 构建树
     *
     * @param preorder 前序遍历的结果
     * @param inorder 中序遍历的结果
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 构造map
        for (int i = 0; i < inorder.length; i++) {
            // key是中序遍历的值，value是值在中序遍历的下标
            indexMap.put(inorder[i], i);
        }
        // 前序遍历和中序遍历的节点个数是一致的，所以选一个就行
        int n = preorder.length;
        TreeNode treeNode = myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
        return treeNode;
    }

    /**
     * 构建树
     *
     * @param preorder 前序遍历
     * @param inorder 中序遍历
     * @param preorder_left 前序遍历最左节点下标
     * @param preorder_right 前序遍历最右节点下标
     * @param inorder_left 中序遍历最左节点下标
     * @param inorder_right 中序遍历最右节点下标
     * @return
     */
    public TreeNode myBuildTree(int[] preorder,
                                int[] inorder,
                                int preorder_left,
                                int preorder_right,
                                int inorder_left,
                                int inorder_right) {
        // 如果前序遍历最左大于最右 返回null
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历，就是跟左右，所以可以找到根节点
        int preorder_root = preorder_left;
        // 定位到中序遍历中根节点的位置
        int inorder_root = indexMap.get(preorder[preorder_root]);
        // 建立根节点
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归构建左子树，并连接到根节点
        // 前序遍历就成第二个节点（之前的第一个节点是根节点）到第二个节点 + 左子树的长度
        // 中序遍历就是最开始的节点，到跟节点前面的节点
        root.left = myBuildTree(preorder,
                inorder,
                preorder_left + 1,
                preorder_left + size_left_subtree,
                inorder_left,
                inorder_root - 1);
        // 递归构建右子树，并连接到根节点
        root.right = myBuildTree(preorder,
                inorder,
                preorder_left + size_left_subtree + 1,
                preorder_right,
                inorder_root + 1,
                inorder_right);
        return root;
    }
}

/**
 * 树的节点
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
